package 数据结构.章节09._151_桶排序;


import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2021/10/10 - 10 - 10 - 11:23
 * @Description: 数据结构.章节09._151_桶排序
 * @Version: 1.0
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] a = new int[]{6,7,3,1,9,10,1};
        new BucketSort().bucketSort(a);
        System.out.println(Arrays.toString(a));
    }
    //数组最大元素
    int maxOfArray(int[] array){
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            max = Math.max(array[i],max);
        }
        return max;
    }
    //hash函数，确定该元素所要放入的桶的下标
    private static int hash(int element, int max, int length){
        return (element * length)/(max + 1);
    }
    private void bucketSort(int[] arr){
        int length = arr.length;
        //创建桶：每个桶实现实质是一个单链表
        LinkedNode[] bucket = new LinkedNode[length];
        //得到元素最大值
        int max = maxOfArray(arr);
        //入桶
        for (int value : arr) {
            //计算桶的下标
            int hash = hash(value, max, length);
            if (bucket[hash] == null) {
                //初始化链表表头
                bucket[hash] = new LinkedNode(value);
            } else {
                //升序形式插入链表，降序调insertDown
                insertUp(value, bucket[hash], bucket, hash);
            }
        }
        //升出桶,回填arr
        int k = 0;
        for(LinkedNode node: bucket){
            if(node != null){
                while(node != null){
                    arr[k++] = node.value;
                    node = node.next;
                }
            }
        }
        /*
        降序出桶形式：
        int cur = 0;
        for (int i = length-1; i >=0 ; i--) {
            LinkedNode p = buckets[i];
            if(p != null){
                while(p != null){
                    array[cur++] = p.value;
                    p = p.next;
                }
            }
        }
         */

    }
    //升序
    private void insertUp(int value, LinkedNode head, LinkedNode[] bucket, int hash) {
        LinkedNode newNode = new LinkedNode(value);
        //放在链表头部
        if(value <= head.value){
            newNode.next = head;
            bucket[hash] = newNode;
            return;
        }
        LinkedNode p = head;
        LinkedNode pre = null;
        //往后找第一个比当前值大的节点，插在它的前面
        while(p != null && value>p.value){
            pre = p;
            p = p.next;
        }
        pre.next = newNode;
        if(p != null){//没到末尾，接上p
            newNode.next = p;
        }
    }
    //降序
    private void insertDown(int value, int index, LinkedNode[] buckets, LinkedNode head){
        LinkedNode newNode = new LinkedNode(value);
        if(value>=head.value){
            buckets[index] = newNode;
            newNode.next = head;
            return;
        }
        LinkedNode p = head;
        LinkedNode pre = null;
        while(p != null && value<p.value){
            pre = p;
            p = p.next;
        }
        pre.next = newNode;
        if(p!=null){
            newNode.next = p;
        }
    }

}
